/**
 * 判断subRoot是否为root树的子树
  */

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //1.若root为空节点则返回false
        if(root == null){
            return false;
        }
        //判断当前子树跟subRoot树是否相同
        if(isSame(root,subRoot)){
            return true;
        }
        //判断当前root的左子树与subRoot子树是否相同,相同返回true
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        //判断当前root的右子树与subRoot子树是否相同,相同返回true
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        //如果都不相同,则返回false
        return false;
    }
    //判断两棵树是否相同
    public boolean isSame(TreeNode p,TreeNode q){
        //1.两个节点均为空
        if(p == null && q == null){
            return true;
        }
        //2.两个节点其中有一个节点为空
        if(p == null || q == null){
            return false;
        }
        //3.两个节点均不为空
        if(p.val != q.val){
            return false;
        }
        //4.只有左右子树都相同的节点的二叉树才相同
        return isSame(p.left,q.left) && isSame(p.right,q.right);
    }
}